from typing import List


class Solution:
    def canCross(self, stones: List[int]) -> bool:
        size = len(stones)
        index = {stone: i for i, stone in enumerate(stones)}

        if stones[1] - stones[0] != 1:
            return False

        dp = [set() for _ in range(size)]

        dp[1].add(stones[1] - stones[0])

        for i in range(1, size):
            stone = stones[i]
            for step in dp[i]:
                if stone + step + 1 in index:
                    dp[index[stone + step + 1]].add(step + 1)
                if stone + step in index:
                    dp[index[stone + step]].add(step)
                if step > 1 and stone + step - 1 in index:
                    dp[index[stone + step - 1]].add(step - 1)

        return len(dp[-1]) > 0


if __name__ == "__main__":
    print(Solution().canCross([0, 1, 3, 5, 6, 8, 12, 17]))  # True
    print(Solution().canCross([0, 1, 2, 3, 4, 8, 9, 11]))  # False
    print(Solution().canCross([0, 2]))  # False
